public class MaximumSubarray0104_53 {

    //超时了了了了了了了了了了了了了了
//    public int maxSubArray(int[] nums) {
//        int sum = Integer.MIN_VALUE;
//        int count = 0;
//
//        for (int i = 0; i<nums.length; i++) {
//            count = 0;
//            for (int j = i; j < nums.length; j++) {
//                count += nums[j];
//                sum = Math.max(sum, count);
//            }
//        }
//        return sum;
//    }


    /**
     * 注意思路：连续和为负数 就跳过 从新开始
     *
     */
    public int maxSubArray(int[] nums) {
        if(nums.length == 1) return nums[0];

        int resultSum = Integer.MIN_VALUE;
        int sum = 0;

        for (int i = 0; i < nums.length; i++) {
            sum = nums[i]+sum;
            resultSum = Math.max(sum,resultSum);

            if(sum < 0){
                sum = 0;
            }
        }
        return resultSum;
    }
}
